package 面试题12_矩阵中的路径.回溯剪枝实现;

/**
 * @Author ：xu_xiaofeng.
 * @Date ：Created in 14:16 2021/2/10
 * @Description：
 */
public class Solution {

    public boolean exist(char[][] board, String word) {
        boolean result = false;

        if (board.length == 0 || word == null) {
            return result;
        }

        boolean[][] visited = new boolean[board.length][board[0].length];

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                result = hasPathCore(board, visited, word, i, j, 0);

                if (result) {
//                    break;
                    return true;
                }
            }
        }

        return result;
    }

    private boolean hasPathCore(char[][] board, boolean[][] visited, String word, int row, int col, int k) {

        // 当前访问的位置是否在矩阵内，并且未被访问
        if (row >= 0 && row < board.length && col >= 0 && col < board[0].length && !visited[row][col]) {

        } else {
            return false;
        }

        // 跳出递归的条件
        if (word.charAt(k) != board[row][col]) {
            return false;
        }
        if (k == word.length() - 1) {
            // 已经找到了所有字符
            return true;
        }

        if (visited[row][col]) {
            return false;
        }

        visited[row][col] = true;
        boolean hasPath = false;

        // 向上下左右4个方向探测
        hasPath = hasPathCore(board, visited, word, row - 1, col, k + 1) //上
                || hasPathCore(board, visited, word, row + 1, col, k + 1)//下
                || hasPathCore(board, visited, word, row, col - 1, k + 1)//左
                || hasPathCore(board, visited, word, row, col + 1, k + 1);//右

//        if (hasPathCore(board, visited, word, row - 1, col, k + 1)) {
//            hasPath = true;
//        } else if (hasPathCore(board, visited, word, row + 1, col, k + 1)) {
//            hasPath = true;
//        } else if (hasPathCore(board, visited, word, row, col - 1, k + 1)) {
//            hasPath = true;
//        } else if (hasPathCore(board, visited, word, row, col + 1, k + 1)) {
//            hasPath = true;
//        }

        if (!hasPath) {
            // 此路不通
            visited[row][col] = false;
        }

        return hasPath;

    }
}
